\begin{enumerate} 
\item[(a)] Let $S$ be a set of elements,  $\oplus$ an associative and commutative binary operation
on $S$, and assume that the product of an element of $S$ by a positive real
value is well defined. Prove that, if $S_1$ and $S_2$ are convex subsets of $S$—that
is, if, $\forall x,y \in S_i$ and $\forall \alpha  0 \le \alpha \le 1$, we have $\alpha \cdot x \oplus (1−\alpha) \cdot y \in S_i$ (for each
$i = 1,$)—, then $S_1 \cap S_2$ is also convex.
\item[(b)] Now consider the intersection of a set $S$ of halfplanes in 2D. From the
first part of this question, this intersection is a convex polygon (possibly
unbounded). Show how to compute the intersection in $O(|S| \log |S|)$ time.
\item[(c)] If that intersection polygon has n edges, then only $n$ halfplanes are needed
to define it; any halfplane of $S$ that does not contribute an edge to intersection
polygon is called redundant. Prove that every redundant halfplane
contains the intersection of two halfplanes from $S$ (possibly themselves redundant).
\item[(d)] If the intersection polygon has $n$ edges, is it possible to compute it in
$O(n \log |S|)$ time? in $O(|S| \log n)$ time? If the worst-case remains unchanged,
would randomization help?
\end{enumerate}

\vspace{10pt}

\begin{enumerate} 
\item[(a)] So we're given that $S_1$ and $S_2$ are convex subsets of $S$, and need to prove that $S_1 \cap S_2$ is also convex.

Let's consider two arbitrary elements $x$ and $y$ from  $S_1 \cap S_2$. By definition of $S_1 \cap S_2$, $x \in S_1,S_2$ and $y \in S_1,S_2$. But because $S_1$ and $S_2$ are convex sets, then $\forall \alpha \quad  0 \le \alpha \le 1$ we have $z = \alpha \cdot x \oplus (1−\alpha) \cdot y \in S_1, S_2$. So $z$ by definition is in $S_1 \cap S_2$. As in holds for any two elements of $S_1 \cap S_2$ and for any $\alpha \quad  0 \le \alpha \le 1$, then $S_1 \cap S_2$ is convex, what we wanted to show.

\item[(b)] Suppose we're given the set $S$ of halfplanes in 2D, and we want to find the intersection of them.

Let's use the divide and conquer approach:

$Intersect(S)$
\begin{enumerate}
\item[0 .] \textbf{If} $|S| = 1$ \textbf{ return } $S$
\item[0$^\prime$.] \textbf{If} $|S| = 2 = \{h_1, h_2\}$ \textbf{return}  $h_1 \cap h_2$
\item[1 .] randomly divide the given set into 2 equalled by size subsets $S_1$ and $S_2$
\item[2 .] find the intersections in both subsets: $I_1 = Intersect(S_1)$ and $I_2 = Intersect(S_2)$
\item[3 .] \textbf{return} the intersection $I_1 \cap I_2$
\end{enumerate}

The zero step require constant time.

The first step of dividing the set into two equalled part is linear ($O(|S|)$), as we can for each halfplane in $S$ decide randomly whether it will go into one part or another.

The second step implies the recursion calls, that is, if the time for computation the intersection of set $S$ is $T(|S|)$, then this step will require $2  T(\frac{|S|}{2})$.

We need to show that the third step is also linear. In this case the computation time of this algorithm will satisfy the following recurrence equation:

$$T(|S|) = 2 T(\frac{|S|}{2}) + O(|S|)$$

That equation has the solution $O(|S| \log |S|)$, the desired complexity.

\vspace{5pt}

Let's show now that the intersection of two found intersections is actually can be computed in linear time ($O(|S|)$).

Suppose we are given two found intersections. From the previous question we know that they will be convex, so what we want to do is to construct the intersection of two convex polygons, taking into account that they can be opened.

First, let's consider the algorithm that will find the intersection of two closed convex polygons $P$ and $Q$\footnote{http://www.iro.umontreal.ca/~plante/compGeom/algorithm.html}:

\begin{enumerate}
\item[1.] Construct the convex hull of the union of $P$ and $Q$;
\item[2.] For each pocket lid of the convex hull, find the intersection of $P$ and $Q$ that lies in the pocket;
\item[3.] Merge together the polygonal chains between the intersection points found in 2.
\end{enumerate}

\begin{center}
    \includegraphics[width=100mm]{p4_pockets.png} 
\end{center}

A \textbf{pocket lid} is a line segment belonging to the convex hull of the union of $P$ and $Q$, but which belongs to neither $P$ nor $Q$. It should connect a vertex of $P$ with a vertex of $Q$, because if it were to connect two vertices of $P$, then $P$ would not be convex, since the lid lies on the convex hull and is not a segment of $P$. 

The first step of constructing the convex hull of two convex polygons is linear of the size of those polygons, as was shown on the lecture.

Let's consider in more detail the second step. Each pocket lid should close one the intersections of $P$ and $Q$, as its vertices are in different polygons. The pockets themselves form a very special type of polygon:a polygon composed of two concave chains sharing a common vertex at one extremity, and connected by a segment (the found pocket lid) at the other end.

So the algorithm would be the following:

Let's denote the current cutting edge as $ce = \{P_i,Q_j\}$. At first it is the found pocket lid, but then will go closer to the intersection step by step changing one of its vertices to the next one in direction to the intersection.

\begin{algorithmic}[1]

\WHILE { $\{P_i,P_{i+1}\}$ and $\{Q_j,Q_{j-1}\}$ are not intersected}
%\verb'{'
\STATE	$\alpha = \angle Q_jP_iP_{i+1}$
\STATE	$\beta = \angle P_iQ_jQ_{j-1}$
\IF { $\alpha < \beta$}
\STATE		$i = i + 1$ \quad //shift the vertex of cutting edge from $P$ to the next one
\ELSIF {$\beta < \alpha$}
\STATE			$j = j - 1$ \quad //shift the vertex of cutting edge from $Q$ to the next one
\ELSE 
\STATE $i = i+1$;
\STATE $j = j+1$;
\ENDIF
%\verb'}'
\ENDWHILE

\RETURN found intersection point
\end{algorithmic}

\input{p4_f2.tex}

As at each step we are going closer to the intersection, than the time complexity of this algorithm is $O(l+s)$, where $l$ is the number of segments in $P$ before intersection point and $s$ is the number of segments in $Q$ before intersection point.

It is clear that overall all pockets can include at most all segments of two initial convex polygons, so finding all the intersections within pockets will cost $O(|P|+|Q|)$.

On the third step of initial algorithm on which we need to merge found chains we'll need to actually traverse the intersection, which is again of size $O(|P|+|Q|)$, so this step is also linear.

So the overall algorithm of merging two closed convex polygons is linear of their size.

\vspace{5pt}
Let's consider the case of merging two convex polygons, when they can be opened.

For each of the opened convex polygon we can have 5 cases:
\begin{enumerate}
\item[1.] the opened polygon is the halfplane (no vertices)
\item[2.] the opened polygon is the area among two parallel lines (no vertices)
\item[3.] the opened polygon is the area among two rays with angle $\le 180^\circ$ (1 vertex)
\item[4.] the opened polygon is the area constructed as the intersection of 3 halfplanes, defining lined not intersected in the same point  (2 vertices)
\item[5.] the opened polygon can be represented as the union of closed convex polygon and the opened part represented as in 4. (more than 2 vertices)
\end{enumerate}

There cannot be other cases, because if the polygon is convex and opened simultaneously its boundary can contain at most two rays: first 4 cases describes the situations with less than 4 halfplanes, when we add the new halfplane to the current configuration to remain opened it should include the parts of those rays going to the infinity, defining new rays. So the part which is bounded by those rays and the segment between their vertices has the form described in the case 4, and remaining part has to be closed (as we include the opened part in the other side) and convex.

\vspace{5pt}
If one of the polygons (suppose $P$) has the form from cases 1-4, it's obvious that the time of finding the intersection is linear, as we need for all edges of $P$ try to find the intersection with all edges of $Q$. As $P$ contains bounded number of edges now, the finding intersection will cost $O(|Q|)$.
 
In the worst case we are given two opened convex polygons $P$ and $Q$ from the 5th case. Let's split those polygons into parts $P = P_o \cup P_c$, $Q = Q_o \cup Q_c$. Then we'll find four intersections $ P_o \cap Q_o$,  $ P_o \cap Q_c$,  $ P_c \cap Q_o$,  $ P_c \cap Q_c$, the time of finding each of them is linear. Then we'll need to construct the union of those four intersections, that also can be done in linear time as they will represent adjacent areas which we'll need just to trace.

So finding the intersection of two convex polygons is linear, and thus, the overall algorithm will take $O(|S| \log |S|)$, as was described above.

\item[(c)] Suppose we know the intersection of all halfplanes in $S$ (let's denote it $I$). Let's consider arbitrary redundant halfplane  $h$ from $S$, then we know that it is not in the set $I_h$ of the halfplanes defining $I$.

If this set contains only one halfplane $h^\prime$, than by definition of $I$ $h \cap h^\prime = h^\prime \subset h$.

If the set $I_h$ contains more than one halfplane it means that the intersection $I$ has vertices on the boundary and all of them are points of intersection of two lines defining halfplanes from $I_h$. So among these vertices we can find those that are the closest to the line defining $h$.

If it is only one vertex, than it defines the intersection of two halfplanes $h_1$ and $h_2$ which we know is entirely within the given halfplane $h$, as no another point of $h_1 \cap h_2$ can be closer to the $h$ and thus cannot be from the other side from it.

If there are some vertices which are the closest ones to the line defining $h$, it means, that $I_h$ contains the segment parallel to the line defining $h$. This segment have to be defined also by one the halfplanes from $S$, suppose it would be  $h^\prime$. So $h^\prime \subset h$ and thus,  $h \cap h^\prime \subset h$.

\item[(d)] In the worst-case analysis it's not possible to compute the intersection of the set $S$ in  $O(n \log |S|)$ time or $O(|S| \log n)$ time, where $n$ is the size of intersection. As there always can be the case where the size of final intersection is quite small (suppose $3$), and all other halfplanes are just redundant, but during the intermediate steps we'll need to calculate the intersection of all others, which size can include all the intermediate halfplanes.

Randomization also will not help as at each step of merging of the two found intersections we'll need to calculate in any case the convex hull, which is $O(|S|)$ in the common case, and we still need to do $\log(|S|)$ recurrence step to get the full solution.

\end{enumerate}

